package leetcode;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-25 15:56
 **/
public class LeetCode416 {

    public boolean canPartition(int[] nums) {
        int n = nums.length;
        //存储nums中所有元素的和,如果和为奇数,直接返回false
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        if ((sum & 1) == 1) {
            return false;
        }

        //和的一半
        int target = sum / 2;

        //boolean[i][j]: 表示是否可以从索引0 - i下标中取出元素使得其和为j,只要存在0-i索引中可以取出元素值为target,则返回true
        boolean[] dp = new boolean[target + 1];

        //便于后续判断的时候,nums[i]刚好为j的时候的一个优化
        dp[0] = true;

        //如果索引为0的元素小于等于target,则dp[0][nums[0]] = true;
        //当索引为0时,只能使其和为nums[0]
        if (nums[0] <= target) {
            dp[nums[0]] = true;
        }

        for (int i = 1; i < n; ++i) {
            int num = nums[i];
            for (int j = target; j >= num; --j) {
                //看当前元素,如果当前元素<=j,dp[i][j] |= dp[i - 1][j - nums[i]]
                //第二层的循环我们需要从大到小计算，因为如果我们从小到大更新 dp 值，那么在计算 dp[j] 值的时候，dp[j−nums[i]] 已经是被更新过的状态，不再是上一行的 dp 值。

                dp[j] |= dp[j - num];
            }

            //如果0-i中可以取出元素使得何为target,则直接即可返回true
            if (dp[target]) {
                return true;
            }
        }

        return false;
    }

    //小优化
    /*public boolean canPartition(int[] nums) {
        int n = nums.length;
        //存储nums中所有元素的和,如果和为奇数,直接返回false
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        if ((sum & 1) == 1) {
            return false;
        }

        //和的一半
        int target = sum / 2;

        //boolean[i][j]: 表示是否可以从索引0 - i下标中取出元素使得其和为j,只要存在0-i索引中可以取出元素值为target,则返回true
        boolean[][] dp = new boolean[n][target + 1];

        //便于后续判断的时候,nums[i]刚好为j的时候的一个优化
        dp[0][0] = true;

        //如果索引为0的元素小于等于target,则dp[0][nums[0]] = true;
        //当索引为0时,只能使其和为nums[0]
        if (nums[0] <= target) {
            dp[0][nums[0]] = true;
        }

        for (int i = 1; i < n; ++i) {
            for (int j = 0; j <= target; ++j) {
                //不看当前元素,那么dp[i][j] = dp[i - 1][j]
                dp[i][j] = dp[i - 1][j];

                //看当前元素,如果当前元素<=j,dp[i][j] |= dp[i - 1][j - nums[i]]
                if (j >= nums[i]) {
                    dp[i][j] |= dp[i - 1][j - nums[i]];
                }
            }

            //如果0-i中可以取出元素使得何为target,则直接即可返回true
            if (dp[i][target]) {
                return true;
            }
        }

        return false;
    }*/

    //动态规划最初版
    /*public boolean canPartition(int[] nums) {
        int n = nums.length;
        //存储nums中所有元素的和,如果和为奇数,直接返回false
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        if ((sum & 1) == 1) {
            return false;
        }

        //和的一半
        int target = sum / 2;

        //boolean[i][j]: 表示是否可以从索引0 - i下标中取出元素使得其和为j,只要存在0-i索引中可以取出元素值为target,则返回true
        boolean[][] dp = new boolean[n][target + 1];

        //如果索引为0的元素小于等于target,则dp[0][nums[0]] = true;
        //当索引为0时,只能使其和为nums[0]
        if (nums[0] <= target) {
            dp[0][nums[0]] = true;
        }

        for (int i = 1; i < n; ++i) {
            for (int j = 0; j <= target; ++j) {
                //不看当前元素,那么dp[i][j] = dp[i - 1][j]
                dp[i][j] = dp[i - 1][j];

                //看当前元素,如果当前元素=j,那么dp[i][j] = true
                if (nums[i] == j) {
                    dp[i][j] = true;
                    continue;
                }

                //看当前元素,如果当前元素<j,dp[i][j] |= dp[i - 1][j - nums[i]]
                if (j > nums[i]) {
                    dp[i][j] |= dp[i - 1][j - nums[i]];
                }
            }

            //如果0-i中可以取出元素使得何为target,则直接即可返回true
            if (dp[i][target]) {
                return true;
            }
        }

        return false;
    }*/

}
